package main.java.Fzy.Work.task01;

import java.util.Arrays;

public class Demo01 {
    public static void main(String[] args) {

        int[] arr = new int[10];
        for (int i = 0; i < 10; i++) {
            arr[i] = (int) (Math.random()*100);
        }
        System.out.println("排序前: "+ Arrays.toString(arr));

//        int start = (arr.length-1)/2;
//
//        //最大堆构建
//        for (int i = start;i>=0;i--){
//            toMaxHeap(arr,arr.length,i);
//        }
//        for(int i = arr.length-1;i>0;i--){
//            int t = arr[0];
//            arr[0] = arr[i];
//            arr[i] = t;
//            toMaxHeap(arr,i,0);
//        }
        quickSort(arr,0,arr.length-1);

        System.out.println("排序后："+Arrays.toString(arr));

    }

    /**
    * @author LazyCat
    * @date  2022/10/31
    * @param arr: 排序数组,  size:数组长度   index: 当前头结点
    * @return
     * 堆的创建与维护
    */
    private static void toMaxHeap(int[] arr,int size,int index){

        int left = index*2+1;
        int right = index*2+2;

        int maxIndex = index;

        if(left<size && arr[left]>arr[maxIndex]){
            maxIndex = left;
        }
        if(right<size && arr[right]>arr[maxIndex]){
            maxIndex = right;
        }

        if(maxIndex != index){
            int t = arr[maxIndex];
            arr[maxIndex] = arr[index];
            arr[index] = t;
            toMaxHeap(arr,size,maxIndex);
        }
    }


    /**
    * @author LazyCat
    * @date  2022/10/31
    * @param
    * @return
     * 快速排序
    */

    private static int[] quickSort(int[] arr,int right,int left){

        int start = right;
        int end = left;
        int key = arr[right];

        //第一次基准
        while (end>start){
            //从后向前比较
            while (end > start && arr[end]>=key){
                end--;
            }
            //发现较小值进行交换
            if (arr[end] <= key) {
                int temp = arr[end];
                arr[end] = arr[start];
                arr[start] = temp;
            }
            //从前向后比较
            while (end>start && arr[start]<=key){
                start++;
            }
            if(arr[start] >= key){
                int temp = arr[start];
                arr[start] = arr[end];
                arr[end] = temp;
            }
        }
        if(start>right){
            quickSort(arr,right,start-1);
        }
        if(end<left){
            quickSort(arr,end+1,left);
        }
        return arr;
    }
}
